package book;

import java.util.Arrays;
import java.util.Scanner;

public class PrimesSolution {

    // 判断x是否质数，返回true表示x是质数，否则返回false
    boolean isPrime(int x) {
        for (int p = 2; p < x; p++) 
            if (x % p == 0)
                return false; // 找到p为x的因子，x不是质数
        return true; // 未找到因子，x为质数
    }

    // 方法1：求n以内的所有质数并输出
    void listPrimes1(int n) {
        for (int x = 2; x <= n; x++)
            if (isPrime(x)) // 判断是否质数的算法在isPrime方法中实现
                System.out.print(" " + x);
        System.out.println();
    }

    // 方法2：备忘录优化
    void listPrimes2(int n) {
        boolean[] nums = new boolean[n + 1];
        Arrays.fill(nums, true);
        for (int x = 2; x <= n; x++)
            if (true == nums[x]) {
                System.out.print(" " + x); // x 为质数
                for (int y = x + x; y <= n; y += x)
                    nums[y] = false; // x的倍数均为合数
            }
        System.out.println();
    }

    public static void main(String[] args) {
        System.out.print("请输入n，让我计算n以内的所有质数：");
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        scan.close();
        new PrimesSolution().listPrimes2(n);
    }
}
